package z_exam;

import java.math.BigInteger;
import java.util.Arrays;

/**
 * @Author: 海琳琦
 * @Date: 2021/12/15 21:54
 */
public class test {

    public static void main(String[] args){
        boolean validIPv4 = isValidIPv4("1.2.3.4");
        System.out.println(validIPv4);
        int A[] = {49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15, 35, 25, 53, 51};
        heapSort(A, A.length, 3);
        int[] ints = Arrays.copyOfRange(A, A.length - 3, A.length);
        System.out.println(Arrays.toString(ints));
        BigInteger bg = new BigInteger("eeeeedddddccccc11111", 16);
        String string = bg.toString(10);
        System.out.println(string);
        int[] ints1 = mergeSort(A);
        System.out.println(Arrays.toString(ints1));
    }

    public static boolean isValidIPv4(String queryIP) {
        int queryIPLength = queryIP.length();
        if (queryIPLength == 0) {
            return false;
        }
        if (queryIP.charAt(0) == '.' || queryIP.charAt(queryIPLength - 1) == '.') {
            return false;
        }
        if (queryIP.indexOf('+') >= 0 || queryIP.indexOf('-') >= 0) {
            return false;
        }
        String[] array = queryIP.split("\\.");
        if (array.length != 4) {
            return false;
        }
        int length = array.length;
        for (int i = 0; i < length; i++) {
            String numStr = array[i];
            if (numStr.length() == 0 || numStr.length() > 3 || numStr.length() > 1 && numStr.charAt(0) == '0') {
                return false;
            }
            try {
                int num = Integer.parseInt(numStr);
                if (num > 255) {
                    return false;
                }
            } catch (NumberFormatException ex) {
                return false;
            }
        }
        return true;
    }


    public static int[] mergeSort(int[] array) {
        if (array.length < 2) {
            return array;
        }
        int mid = array.length / 2;
        int[] left = Arrays.copyOfRange(array, 0, mid);
        int[] right = Arrays.copyOfRange(array, mid, array.length);
        return merge(mergeSort(left), mergeSort(right));
    }

    private static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        for (int i = 0, j = 0, index = 0; index < result.length; index++) {
            if (i >= left.length) {
                result[index] = right[j++];
            } else if (j >= right.length) {
                result[index] = left[i++];
            } else if (left[i] > right[j]) {
                result[index] = right[j++];
            } else {
                result[index] = left[i++];
            }
        }
        return result;
    }


    /**
     * 堆排序
     */
    public static void heapSort(int array[], int n, int k){
        //建立一个大根堆
        buildHeap(array, n);
        while (n > 1 && k >= 0) {
            // 将堆顶元素与堆的最后一个元素互换，并从堆中去掉最后一个元素
            swap(array, 0, --n);
            // 从新的堆顶元素开始向下进行堆调整，时间复杂度O(logn)
            heapify(array, 0, n);
            k--;
        }
    }

    /**
     * 将array[0..n-1]调整成大根堆
     */
    public static void buildHeap(int[] array, int n){
        for(int i = n / 2 -1; i >= 0; i--){
            heapify(array, i, n);
        }
    }

    public static void heapify(int[] array, int i, int n){
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        // 选出当前结点与其左右孩子三者之中的最大值
        int maxIndex = i;
        if(left < n && array[left] > array[maxIndex]){
            maxIndex = left;
        }
        if(right < n && array[right] > array[maxIndex]){
            maxIndex = right;
        }
        if(maxIndex != i){
            // 把当前结点和它的最大(直接)子节点进行交换
            swap(array, i, maxIndex);
            // 递归调用，继续从当前结点向下进行堆调整
            heapify(array, maxIndex, n);
        }
    }

    public static void swap(int[] array, int i, int j){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

}
